The present invention relates to digital communications, and more particularly, to methods and systems for detecting and correcting erasure errors in data transmitted via packet-based networks.
As the speed and performance of the public Internet improve, it becomes an increasingly viable option for transmitting Constant Bit Rate (CBR) data and other selected types of “real-time” data. CBR data includes data such as voice, video, and professional, studio quality (i.e., program) audio. Typically, constant bit rate (CBR) data is formatted into 64 kbps time-slots (TS) and TDM techniques are used to map the time-slots into T1 or E1 frames which are transported over the Public Switched Telephone Network (PSTN). Over time, improvements in Internet Quality of Service (QoS) will transform the public Internet into a low cost, general-purpose multimedia transport medium.
Packet-based distribution of CBR data can thus provide a cost-effective alternative to traditional distribution, which relies on dedicated transmission paths over the Public Switched Telephone Network (PSTN). Such dedicated lines typically incur high recurring monthly costs, or require the use of scarce RF spectrum.
The economic advantage of IP networks derives from the fact that multiple packets streams within the packet network are statistically multiplexed onto shared common circuits. The PSTN, on the other hand, requires streams to have dedicated or nailed up circuits connected end-end.
Although an economic motivation exists for transporting CBR data over packet networks, certain impairment issues inherent in packet networks must be addressed if packet networks are to effectively function as an alternative to transport over traditional dedicated circuits
Packet networks were designed primarily to provide a “Best-Effort” service. A Best-Effort service is defined as a service that does not guarantee performance metrics such as end-to-end delay, packet jitter and packet loss, within the packet stream. This is because a packet network works to get packets from point A to point B without regard to the particular path from point A to point B. Specific packets within a data stream may take separate paths to the destination, so that the data stream must be reconstructed once all of the packets arrive at the destination. Due to this best-effort model, the reliability of packet networks to date has been significantly less then what the PSTN network has provided. In general, a packet network exhibits high packet loss rates as well as large packet delay and packet jitter. By comparison, the existing PSTN infrastructure provides an extremely reliability transport system with availability of 99.999%. Error rates the PSTN exhibits are typically on the order of 10−9, and delay and jitter are tightly controlled. In order to transmit CBR and other Real-Time data via packet networks, communication systems must employ various mechanisms to mitigate the effects of these network impairments.
For non-interactive transmissions, such as radio or television broadcast, latency is of considerably less importance than reception quality, so in the case of a packet loss, the use of Automatic Request for Retransmission (ARQ) or Forward Error-Correction (FEC) is appropriate. For interactive data, however, the delay that a retransmission imposes is not acceptable, and a low-latency FEC provides a more suitable network impairment mechanism.
Although packets can be lost due to transmission errors at the data link level, the primary source of packet losses is congestion in the packet switches and routers. Protocols such as TCP and RTP associate a sequence number with each packet within the packet header. When a packet becomes corrupted, or when a router drops a packet due to congestion, the communications equipment at the destination can determine which packets are missing by observing the sequence numbers. These types of errors (i.e., lost packets) are referred to herein as Packet Erasures. An important difference between packet erasures and traditional bit errors is that with packet erasures, the particular missing packet can be identified because of the sequence numbers. With individual bit errors occurring within a data field, a detection scheme (e.g., CRC) can recognize that one or more bits in a field is in error, but typically can not identify the exact location of the corrupted bit or bits.
Many existing FEC schemes are relatively complex, and they require significant processing resources to accomplish the error correction task. For some FEC schemes, the associated complexity is due not only to the sophisticated arithmetic involved with the error corrections, but also to the fact that that they are designed to correct bit errors within a data field without a priori knowledge of the bit error location. One example of such an FEC scheme is a class of FEC codes known as “Reed-Solomon” codes (referred to as RS codes herein). In general, an RS code can correct h/2 erasures, where h is the number of redundant packets generated and sent along with the data packets.
For other FEC schemes that use a priori knowledge of the bit error location as part of the correction algorithm, the complexity is due solely to the associated arithmetic. One example of such an FEC scheme is a RS code that has been adapted to correct for packet erasures, known as Reed-Solomon Erasure (RSE) codes. In general, an RSE code can correct h erasures, where h is the number of redundant packets generated and sent along with the data packets.